The present invention relates to data transmission over error prone transmission lines and, more particularly, to error correcting codes that must include a minimum number of "1" bits in each encoded data word.
There is an increasing demand for high speed digital data transmission within existing telephone facilities. To provide increased digital data transmission, the existing T-carrier facilities have been modified to carry digital data. The T-carrier facilities provide a means for transmitting digital data from a plurality of sources over a single time domain multiplexed transmission link. In a T-carrier system, data streams from a number of channels at a first station are combined into a single time domain multiplexed data stream which is transmitted to a second station where the data is demultiplexed back into separate data streams.
The transmission link between the two stations includes repeaters for correcting for line losses. These repeaters must be synchronized with circuitry in the two stations. This synchronization is maintained by utilizing transitions between "1" and "0" bits to correct timing errors. This method of correcting timing errors places constraints on the data transmitted which will be discussed in more detail below.
Unfortunately, the existing facilities do not always have the transmission quality to allow data to be transmitted with an acceptable error rate. For example, attempts have been made to utilize the existing T-carrier facilities and lines for transmitting high speed data. The T-carrier lines are designed and engineered for a bit error rate of approximately one error in a thousand for 95 percent of the systems. Although this is adequate for voice grade services, it is insufficient for data services which typically require an error rate of one error in 100 million.
One method of improving the error rate of the existing T-carrier facilities is to encode the data using an error correcting code before transmitting it over the T-carrier lines. For the purposes of this discussion, an error correcting code is most easily understood with reference to the transmission of data over an error prone transmission line. Assume that a first user wishes to transmit n-bit data words to a second user over an error prone transmission line. The first user generates data in n-bit data words. There are 2.sup.n possible such data words. Prior to transmission, each data word is converted to an m-bit data word, which will be referred to as a transmission word. Here, it is assumed that m&gt;n. At the other end of the transmission line, the received transmission words are converted back to data words.
Since there are more possible transmission words than data words, not every m-bit transmission word corresponds to a data word. For example, if n=8 and m=16, there are 256 possible data words. However, there are 65,536 possible transmission words. Only 256 of these transmission words correspond to the 256 possible data words. These transmission words will be referred to as legal transmission words. The remaining transmission words will be referred to as illegal transmission words. In an error free transmission system, none of the illegal transmission words would be received by the second user. However, if the transmission system is error prone, a legal transmission word can be converted to an illegal transmission word by a transmission error with changes the value of one or more bits in the transmitted data word.
An error correcting code will be defined to be a transformation for mapping each value of a data word onto the set of 2.sup.n legal transmission words such that errors in transmission can be detected and corrected. That is, the value of the legal transmission word which was corrupted by transmission errors into a received illegal transmission word may be deduced from said illegal transmission word. This error correction is possible provided the number of errors introduced into the original legal transmission word is less than a predetermined number which depends on the code in question.
The ability of an error correcting code to correct errors is measured by a quantity referred to as the "Hamming Distance" associated with the code. For example, codes with a Hamming Distance of 5 can detect errors resulting from 4 single-bit errors in transmission and correct for all possible 2 single-bit errors. Error correcting codes of this type are well known to those skilled in the telephone and computer arts. A discussion of error correcting codes may be found in ERROR CORRECTING CODES, 2ND EDITION, by Peterson and Weldon, MIT PRESS, 1972, or in PRACTICAL ERROR DESIGN FOR ENGINEERS, by Neil Glover, Data Systems Technology Corp., 1982.
This type of error correction is utilized in T-carrier facilities to improve the effective transmission error rate. Typically, an 8-bit data word is first encrypted to form a 16-bit data word using an error correcting code. The 16-bit data word is then transmitted over the T-carrier lines. Since there are now twice as many bits to transmit, two "time slots" on the T-carrier lines must be used. That is, each 16-bit transmission word is divided into two 8-bit transmission words. The first such transmission word is transmitted on a first channel in the T-carrier and the second such transmission word is transmitted on a second channel. At the receiving end of the transmission line, the two 8-bit transmission words are recombined into a single 16-bit transmission word. This 16-bit transmission word is then decrypted at the far end of the T-carrier lines to produce the original 8-bit data word. The decryption process also corrects for most of the random bit errors.
One problem with this approach to reducing the error rate on the T-carrier lines is that all encrypted values of the original 8-bit data word do not have sufficient numbers of "1" bits in the 16-bit encrypted words to satisfy the timing constraints in the T-carrier system. As noted above, the T-carrier facilities include circuitry for repeating the data transmitted over long T-carrier lines. These circuits require that the signals being sent over the T-carrier lines include a minimum density of "1" bits, since transitions between "0" and "1" bits are used for recovering from timing errors. As a result, long strings of "0" bits interfere with synchronization.
In general, there must be at least one "1" bit in each group of 16 bits transmitted. As noted above, each data word is transformed into two transmission words which are transmitted on different time channels. Hence, a code that produced a transmission data word which was 16 zeros would be unacceptable if the two 8-bit transmission words were in adjacent time channels.
In addition, an error correcting code that produced one 8-bit transmission word that was all zeros would also be unacceptable. Consider a system in which four channels in the T-carrier are used for error correcting code encrypted data transmission corresponding to two different users, and assume that for a particular 8-bit data word, the first of the resulting 8-bit transmission words was all zeros. If the channels in question were assigned such that the first channel transmitted the first 8-bit transmission word of the first user and the second channel transmitted the first 8-bit transmission word of the second user, then 16 consecutive zeros would be present on the transmission line whenever both users transmitted the 8-bit data word in question at the same time.
In general, the time channels assigned to each of the 8-bit transmission words can not be predicted in advance. Hence, an error correcting code that produced an 8-bit transmission word that was all zeros would also be unacceptable.
Existing error correcting codes do not provide a suitable density of "1" bits. Error correcting codes that generate transmission words that include at least one 1 in each 16 bits are known. However, codes that guarantee at least one 1 in each of the 8-bit transmission words are not known to the prior art. That is, there is always at least one value for an 8-bit data word for which one of the corresponding 8-bit transmission words is all zeros.
In prior art systems, this problem is overcome by limiting the user to 7-bit data words. For example, if the eights bit of each 8-bit data word is a "1", then codes having sufficient numbers of bits containing ones in the 16-bit encrypted data words are known. The problem with this approach is that it reduces the effective Baud rate of the transmission line. If the 8th bit must always be a "1", then there are only 7 bits left to transmit real data. As a result, 1/8 of the capacity of the lines is lost. Hence, a T-carrier facility that has a maximum Baud rate of 64 Kbits/sec can only transmit 56 Kbits/sec of real data.
Broadly, it is an the object of the present invention to provide an improved data transmission system.
It is another object of the present invention to provide an error correcting code that provides sufficient density of "1" bits for timing recovery without restricting the data values transmitted and without reducing the error correcting ability of the code.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the present invention and the accompanying drawings.